package offer.offer02;

import java.util.Stack;

/**
 * 使用自定义的内部类Node来模仿栈, private一个Node指向栈顶, 一个Node指向最小的值,
 * 如果pop出了最小值则扫描整个栈来找新的最小值。
 * 要求时间复杂度O(1), 但是因为pop出的值为最小值的情况并不多, 实际上并不会经常扫描整个栈。
 */
public class Solution30 {//实不相瞒, 这是个stack类
    private Node minNode;
    private Node curNode;

    // 用了个内部类, 没必要
    private class Node{
        private int val;
        private Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    public Solution30() {
        
    }

    public void push(int x) {
        Node tmpNode = new Node(x);
        if(this.curNode == null){
            this.curNode = tmpNode;
            this.minNode = tmpNode;
        }else {
            tmpNode.next = this.curNode;
            this.curNode = tmpNode;
            //判断是否最小值
            if(x < this.minNode.val){
                this.minNode = tmpNode;
            }
        }
    }

    public void pop() {
        Node toPop = this.curNode;
        this.curNode = this.curNode.next;
        if(toPop == this.minNode){
            this.minNode = this.curNode;
            Node tmpNode = this.curNode;
            while (tmpNode != null){
                if(tmpNode.val < minNode.val)
                    this.minNode = tmpNode;
                tmpNode = tmpNode.next;
            }
        }
    }

    public int top() {
        return this.curNode.val;
    }

    public int min() {
        return this.minNode.val;
    }

    public static void main(String[] args) {
        Solution30 solution30 = new Solution30();
        solution30.push(-2);
        solution30.push(0);
        solution30.push(-3);
        System.out.println(solution30.min());
        solution30.pop();
        System.out.println(solution30.top());
        System.out.println(solution30.min());
    }
}

// 猛男落泪, 落泪。
class MinStack {
    Stack<Integer> A, B;
    public MinStack() {
        A = new Stack<>();
        B = new Stack<>();
    }
    public void push(int x) {
        A.add(x);
        if(B.empty() || B.peek() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.pop().equals(B.peek()))
            B.pop();
    }
    public int top() {
        return A.peek();
    }
    public int min() {
        return B.peek();
    }
}

